Problem 160 Intersection of Two Linked Lists
该问题属于链表交叉问题,条件包括在选出交叉结点时不能改变原链表的结构,这也就意味着不能使用反转链表再从尾部回溯的方法.同时链表也不存在环
主要思路:
该问题分为几种情况:
- 两链表有一链表为空,此时返回null
- 两链表均不为空,则先想到由于要求两结点相同之后所有结点都要相同,故至少要让两个链表在距离尾部相同距离的时候才开始判断,否则长度不一必不满足条件。所以先实现一个listLength用于获得链表的长度,将较长的链表指针从头部移动到与较短链表头部相同长度的位置,此时开始比较。若出现相同结点则进行记录,以该记录点为起始,我在此设置了flag用于判断是否需要重设交叉结点,因为此处可能出现第一次出现相同结点后,出现不同结点的情况,如果后续又出现相同结点,则再次设置为交叉结点.如果两链表始终不相交则返回null
注意事项:
在该问题中判断的是两个结点是否属于相同对象,即引用,而不是值相同,所以在例1中两个链表的值1相同,但是相交叉的点是在8.此时只需要将判断的nodeA==nodeB转换为nodeA.val==nodeB.valj即可
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public int listLength(ListNode head){
ListNode temp = head;
int length = 0;
while (temp!=null){
length+=1;
temp = temp.next;
}
return length;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null){
return null;
}else{
int lengthA = listLength(headA);
int lengthB = listLength(headB);
if (lengthA>lengthB){
for(int i=0;i<lengthA-lengthB;i++){
headA = headA.next;
}
}else if (lengthB>lengthA){
for(int i=0;i<lengthB-lengthA;i++){
headB = headB.next;
}
}
ListNode result = null;
boolean flag = true;
while (headA!=null){
if(headA==headB&&flag){
result = headA;
headA = headA.next;
headB = headB.next;
flag = false;
}else{
headA = headA.next;
headB = headB.next;
if(headA==null){
break;
}
if(headA!=headB){
result = null;
flag = true;
}
}
}
return result;
}
}
}
Problem 203 Remove Linked List Elements
该问题属于在链表中删除指定值结点的问题
主要思路:
该问题分为以下几种情况:
- 指定值结点在开头
- 指定值结点在结尾
- 指定值结尾在中间
对于以上每种情况:
- 当指定值在开头时可以直接移动head指针,利用head=head.next移动,考虑到开头可能有多个相同值的结点,此处可以考虑使用while处理跳过这些结点
- 当指定值在结尾时记得判断结点为null条件即可,此处容易发生越界错误
- 当指定值在中间时,主要判断有多个相同值结点连续排列,比如在[1,2,3,5,5,5,6,7,8]中要删除5,只需要在检测到第一个5之后利用while循环移动p.next=p.next.next,循环结束之后再使用p=p.next这样就能将p直接指向指定值结点全结束之后的那个结点。比如检测到第一个5之后,由于我使用了p.next.val来和val比较,故此处p仍在3处,由于检测到5,则p.next=p.next.next,此时p.next移动到第二个5,以此类推移动到最后一个5之后的p.next指向6结束while循环,再将p指向p->next则将p指向了6,之后继续遍历查找直到链尾
注意事项:
- 注意越界问题
- 注意使用临时指针p代替head移动
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null)
return null;
while (head!=null&&head.val==val){
head = head.next;
}
ListNode p = head;
while (p!=null&&p.next!=null){
while(p.next!=null&&p.next.val==val){
p.next = p.next.next;
}
p = p.next;
}
return head;
}
}